The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(O(1), O(n^1)).

(0) Obligation:

Runtime Complexity TRS:
The TRS R consists of the following rules:

0(0(1(x1))) → 0(0(2(1(2(x1)))))
0(0(1(x1))) → 0(0(3(1(4(x1)))))
0(1(0(x1))) → 0(0(1(2(4(x1)))))
0(1(0(x1))) → 2(1(2(0(0(x1)))))
0(1(0(x1))) → 0(0(1(2(2(4(x1))))))
0(1(0(x1))) → 0(0(2(4(1(4(x1))))))
0(4(0(x1))) → 3(4(3(2(0(0(x1))))))
0(0(1(0(x1)))) → 0(0(0(1(4(x1)))))
0(0(4(1(x1)))) → 0(0(2(1(4(x1)))))
0(0(4(1(x1)))) → 0(0(2(1(4(3(x1))))))
0(1(0(4(x1)))) → 0(0(3(4(1(2(x1))))))
0(1(3(0(x1)))) → 0(0(3(1(4(x1)))))
0(1(3(0(x1)))) → 0(3(0(1(2(x1)))))
0(1(3(0(x1)))) → 0(0(1(3(2(5(x1))))))
0(1(4(0(x1)))) → 0(2(0(3(1(4(x1))))))
0(1(5(1(x1)))) → 2(1(1(4(5(0(x1))))))
0(1(5(4(x1)))) → 1(2(4(2(5(0(x1))))))
0(1(5(4(x1)))) → 4(1(0(3(2(5(x1))))))
0(1(5(4(x1)))) → 5(0(2(4(1(4(x1))))))
0(3(0(1(x1)))) → 0(0(3(1(2(2(x1))))))
0(3(1(0(x1)))) → 0(0(3(1(4(x1)))))
0(4(0(1(x1)))) → 0(0(2(1(4(x1)))))
0(4(5(1(x1)))) → 1(2(4(2(5(0(x1))))))
0(4(5(1(x1)))) → 3(1(4(5(0(2(x1))))))
0(4(5(1(x1)))) → 3(2(5(1(4(0(x1))))))
0(4(5(1(x1)))) → 5(3(0(5(1(4(x1))))))
0(4(5(1(x1)))) → 5(5(0(5(1(4(x1))))))
0(4(5(4(x1)))) → 5(2(4(4(0(4(x1))))))
0(5(1(0(x1)))) → 0(0(5(1(2(x1)))))
3(5(0(1(x1)))) → 3(0(2(1(2(5(x1))))))
3(5(1(0(x1)))) → 0(5(1(3(2(x1)))))
3(5(1(0(x1)))) → 2(1(2(0(5(3(x1))))))
3(5(1(0(x1)))) → 3(1(2(2(0(5(x1))))))
3(5(1(0(x1)))) → 5(1(3(2(0(2(x1))))))
0(1(3(3(0(x1))))) → 3(3(2(0(0(1(x1))))))
0(1(3(5(1(x1))))) → 1(1(3(4(5(0(x1))))))
0(1(3(5(1(x1))))) → 1(1(5(0(3(3(x1))))))
0(1(5(2(0(x1))))) → 5(0(3(1(0(2(x1))))))
0(1(5(4(1(x1))))) → 5(3(4(1(0(1(x1))))))
0(1(5(4(4(x1))))) → 4(5(2(1(4(0(x1))))))
0(1(5(4(4(x1))))) → 5(0(4(3(4(1(x1))))))
0(3(1(0(4(x1))))) → 0(0(3(1(2(4(x1))))))
0(4(3(3(0(x1))))) → 0(2(3(4(0(3(x1))))))
0(4(5(2(0(x1))))) → 0(2(2(5(0(4(x1))))))
0(5(1(5(1(x1))))) → 5(5(3(0(1(1(x1))))))
3(0(1(5(4(x1))))) → 0(5(3(4(1(2(x1))))))
3(5(0(1(0(x1))))) → 5(1(2(0(0(3(x1))))))
3(5(4(0(0(x1))))) → 5(0(3(0(4(4(x1))))))
3(5(5(0(1(x1))))) → 5(5(0(3(1(2(x1))))))

Rewrite Strategy: INNERMOST

(1) CpxTrsMatchBoundsProof (EQUIVALENT transformation)

A linear upper bound on the runtime complexity of the TRS R could be shown with a Match Bound [MATCHBOUNDS1,MATCHBOUNDS2] of 1.
The certificate found is represented by the following graph.

Start state: 3110
Accept states: [3111, 3112]
Transitions:
3110→3111[0_1|0]
3110→3112[3_1|0]
3110→3110[1_1|0, 2_1|0, 4_1|0, 5_1|0]
3110→3113[1_1|1]
3110→3118[0_1|1]
3110→3123[1_1|1]
3110→3128[0_1|1]
3110→3133[2_1|1]
3110→3138[0_1|1]
3110→3143[4_1|1]
3110→3148[4_1|1]
3110→3153[5_1|1]
3110→3158[4_1|1]
3110→3163[4_1|1]
3110→3168[0_1|1]
3110→3173[1_1|1]
3110→3178[0_1|1]
3113→3114[0_1|1]
3114→3115[1_1|1]
3115→3116[4_1|1]
3116→3117[3_1|1]
3117→3111[5_1|1]
3117→3118[5_1|1]
3117→3128[5_1|1]
3117→3138[5_1|1]
3117→3168[5_1|1]
3117→3114[5_1|1]
3117→3178[5_1|1]
3118→3119[5_1|1]
3119→3120[4_1|1]
3120→3121[1_1|1]
3121→3122[1_1|1]
3122→3111[2_1|1]
3122→3118[2_1|1]
3122→3128[2_1|1]
3122→3138[2_1|1]
3122→3168[2_1|1]
3122→3114[2_1|1]
3122→3178[2_1|1]
3123→3124[1_1|1]
3124→3125[0_1|1]
3125→3126[3_1|1]
3126→3127[5_1|1]
3127→3111[5_1|1]
3127→3118[5_1|1]
3127→3128[5_1|1]
3127→3138[5_1|1]
3127→3168[5_1|1]
3127→3178[5_1|1]
3128→3129[5_1|1]
3129→3130[2_1|1]
3130→3131[4_1|1]
3131→3132[2_1|1]
3132→3111[1_1|1]
3132→3118[1_1|1]
3132→3128[1_1|1]
3132→3138[1_1|1]
3132→3168[1_1|1]
3132→3164[1_1|1]
3132→3178[1_1|1]
3133→3134[0_1|1]
3134→3135[5_1|1]
3135→3136[4_1|1]
3136→3137[1_1|1]
3137→3111[3_1|1]
3137→3118[3_1|1]
3137→3128[3_1|1]
3137→3138[3_1|1]
3137→3168[3_1|1]
3137→3164[3_1|1]
3137→3178[3_1|1]
3138→3139[4_1|1]
3139→3140[1_1|1]
3140→3141[5_1|1]
3141→3142[2_1|1]
3142→3111[3_1|1]
3142→3118[3_1|1]
3142→3128[3_1|1]
3142→3138[3_1|1]
3142→3168[3_1|1]
3142→3164[3_1|1]
3142→3178[3_1|1]
3143→3144[1_1|1]
3144→3145[5_1|1]
3145→3146[0_1|1]
3146→3147[3_1|1]
3147→3111[5_1|1]
3147→3118[5_1|1]
3147→3128[5_1|1]
3147→3138[5_1|1]
3147→3168[5_1|1]
3147→3164[5_1|1]
3147→3178[5_1|1]
3148→3149[1_1|1]
3149→3150[5_1|1]
3150→3151[0_1|1]
3151→3152[5_1|1]
3152→3111[5_1|1]
3152→3118[5_1|1]
3152→3128[5_1|1]
3152→3138[5_1|1]
3152→3168[5_1|1]
3152→3164[5_1|1]
3152→3178[5_1|1]
3153→3154[2_1|1]
3154→3155[3_1|1]
3155→3156[0_1|1]
3156→3157[1_1|1]
3157→3111[4_1|1]
3157→3118[4_1|1]
3157→3128[4_1|1]
3157→3138[4_1|1]
3157→3168[4_1|1]
3157→3114[4_1|1]
3157→3178[4_1|1]
3158→3159[1_1|1]
3159→3160[4_1|1]
3160→3161[2_1|1]
3161→3162[0_1|1]
3162→3111[5_1|1]
3162→3118[5_1|1]
3162→3128[5_1|1]
3162→3138[5_1|1]
3162→3168[5_1|1]
3162→3114[5_1|1]
3162→3178[5_1|1]
3163→3164[0_1|1]
3164→3165[4_1|1]
3165→3166[4_1|1]
3166→3167[2_1|1]
3167→3111[5_1|1]
3167→3118[5_1|1]
3167→3128[5_1|1]
3167→3138[5_1|1]
3167→3168[5_1|1]
3167→3164[5_1|1]
3167→3178[5_1|1]
3168→3169[4_1|1]
3169→3170[1_1|1]
3170→3171[2_1|1]
3171→3172[5_1|1]
3172→3111[4_1|1]
3172→3118[4_1|1]
3172→3128[4_1|1]
3172→3138[4_1|1]
3172→3168[4_1|1]
3172→3114[4_1|1]
3172→3178[4_1|1]
3173→3174[4_1|1]
3174→3175[3_1|1]
3175→3176[4_1|1]
3176→3177[0_1|1]
3177→3111[5_1|1]
3177→3118[5_1|1]
3177→3128[5_1|1]
3177→3138[5_1|1]
3177→3168[5_1|1]
3177→3114[5_1|1]
3177→3178[5_1|1]
3178→3179[5_1|1]
3179→3180[2_1|1]
3180→3181[4_1|1]
3181→3182[2_1|1]
3182→3114[1_1|1]

(2) BOUNDS(O(1), O(n^1))